﻿#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

//AVLTree   key_value模式
//没有重复数据的key
 

//节点结构
template<class K, class V>
struct AVLTreeNode {

	pair<K, V> _kv;

	AVLTreeNode* _left;
	AVLTreeNode* _right;
	AVLTreeNode* _parent;

	int _bf;//平衡因子balance factor

	AVLTreeNode(const pair<K, V>& kv) 
		:_kv(kv),
		_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_bf(0)
	{}
};


template<class K, class V>
class AVLTree {
public:
	using Node = AVLTreeNode<K, V>;

	bool Insert(const pair<K, V>& kv) {

		if (_root == nullptr) {
			_root = new Node(kv);
			return true;
		}

		Node* parent = _root, * cur = _root;  
		while (cur) {
			if (kv.first > cur->_kv.first)
				cur = cur->_right;
			else if (kv.first < cur->_kv.first)
				cur = cur->_left;
			else return false;

			if (cur) parent = cur;
		}
		//此时cur指向被插入的位置 parent指向被插入位置的父亲节点
		cur = new Node(kv);
		if (kv.first > parent->_kv.first) parent->_right = cur;
		else parent->_left = cur;
		cur->_parent = parent;

		//从cur节点开始向上调整平衡因子 如果不符合情况就得进行旋转操作
		while (parent) {
			if (parent->_left == cur)
				parent->_bf--;
			else
				parent->_bf++;

			if (parent->_bf == 0) break;

			else if (parent->_bf == 1 || parent->_bf == -1) {
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2) {
				//旋转操作

				//1.右单旋
				if (parent->_bf == -2 && parent->_left->_bf == -1) RotateR(parent);
				//2.左单旋
				else if (parent->_bf == 2 && parent->_right->_bf == 1) RotateL(parent);
				//3.左右双旋
				else if (parent->_bf == -2 && parent->_left->_bf == 1) RotateLR(parent);
				//4.右左双旋
				else if (parent->_bf == 2 && parent->_right->_bf == -1) RotateRL(parent);

				else assert(false);
				break;
			}
			else assert(false); 
		}
		return true;
	}

//旋转操作////////////////////////////////////////////////////////////////////////////////////////////////////////////
	void RotateR(Node* parent) {
		//右单旋其实就是把cur的右孩子给parent作为左孩子
		//再让cur作为根节点 parent作为cur的右孩子
		//还得修改一下被改动节点的_parent指针指向
		//然后需要将新的子树根节点与原来指向此子树的根节点的节点进行链接
		Node* Parent = parent;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		Node* P_Parent = Parent->_parent;

		Parent->_left = subLR;
		//subLR可能为空 所以需要判断
		if (subLR != nullptr) subLR->_parent = Parent;

		subL->_right = Parent;
		Parent->_parent = subL;

		//链接原来的AVLTree
		//但是这时候有一个问题 即原来的子树根节点的父亲P_Parent可能是空(对应此时Parent是整个树的根节点)
		if (Parent == _root) {
			_root = subL;
			subL->_parent = nullptr;
		}
		else {
			//此时的新根节点subL不知道是应该插入在P_Parent的左边还是右边 需要判断一下
			if (P_Parent->_left == Parent) P_Parent->_left = subL;
			else P_Parent->_right = subL;
			
			subL->_parent = P_Parent; 
		}

		//更新平衡因子
		//只需要关注被改动的节点即可
		subL->_bf = 0;
		Parent->_bf = 0;

	}

	void RotateL(Node* parent) {
		Node* Parent = parent;
		Node* subR = Parent->_right;
		Node* subRL = subR->_left;

		Node* P_Parent = Parent->_parent;

		Parent->_right = subRL;
		if (subRL != nullptr) subRL->_parent = Parent;

		subR->_left = Parent;
		Parent->_parent = subR;

		if (Parent == _root) {
			_root = subR;
			subR->_parent = nullptr;
		}
		else {
			if (P_Parent->_left == Parent) P_Parent->_left = subR;
			else P_Parent->_right = subR;

			subR->_parent = P_Parent;
		}

		subR->_bf = 0;
		Parent->_bf = 0;
	}

	void RotateLR(Node* parent) {
		Node* Parent = parent;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		int subLR_bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);

		//更新平衡因子是比较复杂的 需要分类讨论
		//具体的分类讨论放在博客上去完成

			//h == 0
			if (subLR_bf == 0) {
				subLR->_bf = 0; 
				Parent->_bf = 0; 
				subL->_bf = 0; 
			}
			//h >= 1
			else if (subLR_bf == -1) {
				subLR->_bf = 0;
				Parent->_bf = 1;
				subL->_bf = 0;
			}
			else if (subLR_bf == 1) {
				subLR->_bf = 0;
				Parent->_bf = 0;
				subL->_bf = -1;
			}
			else assert(false);
		
	}

	void RotateRL(Node* parent) {
		Node* Parent = parent;
		Node* subR = Parent->_right;
		Node* subRL = subR->_left;

		int subRL_bf = subRL->_bf;

		RotateR(parent->_right);
		RotateL(parent);

		if (subRL_bf == 0) {
			subRL->_bf = 0;
			Parent->_bf = 0;
			subR->_bf = 0;
		}
		else if (subRL_bf == 1) {
			subRL->_bf = 0;
			Parent->_bf = -1;
			subR->_bf = 0;
		}
		else if (subRL_bf == -1) {
			subRL->_bf = 0;
			Parent->_bf = 0;
			subR->_bf = 1;
		}
		else assert(false);
	}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


	Node* Find(const K& k) {
		Node* cur = _root;
		while (cur) {
			if (k > cur->_kv.first)
				cur = cur->_right;
			else if (k < cur->_kv.second)
				cur = cur->_right;
			else return cur;
		}
		return nullptr;
	}

	void InOrder() {
		_InOrder(_root);
		cout << endl;
	}

	int Height() {
		return _Height(_root);
	}

	int Size() {
		return _Size(_root);  
	}

	bool IsBalanceTree() {
		return _IsBalanceTree(_root);
	}
private:
	void _InOrder(Node* root) {
		if (root == nullptr) return;
		_InOrder(root->_left);
		cout << "key: " << root->_kv.first << "	" << "value: " << root->_kv.second << endl;
		_InOrder(root->_right);
	}

	int _Height(Node* root) {
		if (!root) return 0;
		size_t LHeigth = _Height(root->_left);
		size_t RHeigth = _Height(root->_right);
		return (LHeigth > RHeigth) ? LHeigth + 1 : RHeigth + 1;
	}

	int _Size(Node* root) {
		if (!root) return 0;
		return _Size(root->_left) + _Size(root->_right) + 1;
	}

	//从下至上进行判断是否为平衡AVL树
	//从上到下也可以 但是效率太低
	bool _IsBalanceTree(Node* root) {
		if (root == nullptr) return true;

		if (_IsBalanceTree(root->_left) && _IsBalanceTree(root->_right)) {
			int LHeight = _Height(root->_left); 
			int RHeight = _Height(root->_right); 
			int diff = (RHeight - LHeight);
			if (abs(diff) >= 2) {
				cout << "cout << root->_kv.first" << "高度差异常" << endl;
				return false;
			}
			else if (diff != root->_bf) {
				cout << "cout << root->_kv.first" << "平衡因子异常" << endl;
				return false;
			}
			else return true;
		}
		else return false;
	}

	Node* _root = nullptr;   
};